package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class Combination {

	static List<List<Integer>> result = new ArrayList<List<Integer>>();
	static List<Integer> list = new ArrayList<Integer>();
	
	
	public static void main(String[] args) {
//		new Combination().combine(4, 2);
//		for (List<Integer> combine : result) {
//			System.out.println(combine);
//		}
//		int[] candidates = {7,3,2};
//		//后来发现要是想要按序输出，可以直接对Arrays排序即可
//		Arrays.sort(candidates);
//		combinationSum(candidates, 18);
//		for (List<Integer> combine : result) {
//			System.out.println(combine);
//		}
//		for (ArrayList<Integer> combine : result1) {
//			System.out.println(combine);
//		}
		letterCombinations("2");
		System.out.println(result2);
	}
	
	
	//all possible of C(n,k), for example C(4,2) is 1,2 . 1,3 . 1,4. 2,3 . 2,4. 3,4
	public List<List<Integer>> combine(int n, int k) {
		if(k > n)
			return null;
		backtracking(n, k, 1);
		return result;
	}

	public void backtracking(int n, int k, int start) {
//		int i,count  ;
//		if(start >= n){
//			return ;
//		}
//		for (i = start, count = 1; i <= n && count <= k; i++, count++) {
//			list.add(i);
//		}
//		result.add(new ArrayList<Integer>(list));
//		list.clear();
//		backtracking(n, k, start + 1);
		if(k < 0){
			return;
		}
		if (k == 0) {
			result.add(new ArrayList<Integer>(list));
			System.out.println(result);
		} else {
			int i ;
			for (i = start; i <= n; i++) {
				list.add(i);
				backtracking(n, k - 1, i + 1);  //寻找下一个
				list.remove(list.size() - 1);
			}
		}
	}
	
	//求组合数C(m, n)
	public long combinationNum(int m, int n) {
		if(n > m){
			return 0;
		}
		if (m == n || n == 0){
			return 1;
		}
		long res = 1;
		int j = 1;
		//将n变为小值
		if(n > m / 2){
			n = m - n;
		}
		//C(m, n) = P(m) / (P(n) * P(m - n))
		//我们已经将n变为小值了，所以等于(m - n + 1) *...*(m)  / P(n)
		
		// Instead of taking factorial, keep on multiply & divide
		for (int i = m - n + 1; i <= m; i++, j++) { 
			res *= i;
			res /= j;
		}
		return res;
	}
	
	static class Comparer implements Comparator<List<Integer>>{

		@Override
		public int compare(List<Integer> o1, List<Integer> o2) {
			int length1 = o1.size();
			int length2 = o2.size();
			int length = Math.min(length1, length2);
			for (int i = 0; i < length; ) {
				if(o1.get(i) < o2.get(i)){
					return -1;
				}else if(o1.get(i) > o2.get(i)){
					return 1;
				}else {
					i++;
				}
			}
			return length1 == length2 ? 0 : length1 - length2;
		}

	}
	
	
	//combination的变体
//	Combination Sum
//	Given a set of candidate numbers (C) and a target number (T), 
//	find all unique combinations in C where the candidate numbers sums to T.
//	The same repeated number may be chosen from C unlimited number of times.（同一个数允许使用多次）
	public static List<List<Integer>> combinationSum(int[] candidates, int sum) {
		if (candidates == null || candidates.length <= 0) {
			return result;
		}
		Arrays.sort(candidates);
		backtrackingOfSum(candidates, sum, 0);
//		Collections.sort(result, new Comparer());
		return result;
	}
	
	//the same method : huiSu. the difference is this time is not a k 
	//but the sum, if has a, to get the sum , you just need sum - a
	//so the parameter remain is sum - a
	//and a number can repeat, so the parameter start can just be i
	public static void backtrackingOfSum(int[] array, int sum , int start) {
		if(sum < 0){
			return;
		}else if (sum == 0) {
//			Collections.sort(list);   //can not do this, because this change the list strcture.
			// and you need to remove the last element.
			ArrayList<Integer> sort =  new ArrayList<Integer>(list);
//			Collections.sort(sort);
			result.add(sort);
//			System.out.println(list);
		}else {
			int i ;
			for (i = start; i < array.length; i++) {
//				System.out.println("sum: " + sum + " i:" + i);
				list.add(array[i]);
				//Because the Number can repeat, so the next start also is i(the combination problem is i + 1);
				backtrackingOfSum(array, sum - array[i] , i);  //寻找下一个
				list.remove(list.size() - 1);
			}
		}
	}
	
	
	
	//combination的变体
//	Combination Sum2
//	Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where 
//	the candidate numbers sums to T.
//	Each number in C may only be used once in the combination（同一个数只允许使用一次，但是C中的同一个数可能有几个）
//	like [10, 1, 2, 7, 6, 1, 5]

	//由于有重复的数字，所以使用set结构
	static Set<ArrayList<Integer>> result2 = new LinkedHashSet<ArrayList<Integer>>();
	static List<Integer> list2 = new ArrayList<Integer>();
	
	
	public static List<List<Integer>> combinationSum2(int[] candidates, int sum) {
		result2.clear();
        list2.clear();
		if (candidates == null || candidates.length <= 0) {
			return new ArrayList<List<Integer>>(result2);
		}
		Arrays.sort(candidates);
		backtrackingOfSum2(candidates, sum, 0);
		return new ArrayList<List<Integer>>(result2);
	}
	
	public static void backtrackingOfSum2(int[] array, int sum , int start) {
		if(sum < 0){
			return;
		}else if (sum == 0) {
			ArrayList<Integer> sort =  new ArrayList<Integer>(list2);
			result2.add(sort);
		}else {
			int i ;
			for (i = start; i < array.length; i++) {
				list2.add(array[i]);
				//Because the Number can't repeat, so the next start also is i + 1;
				backtrackingOfSum2(array, sum - array[i] , i + 1);  //寻找下一个
				list2.remove(list2.size() - 1);
			}
		}
	}
	
	
	//leetcode：17. Letter Combinations of a Phone Number
	//Given a digit string, return all possible letter combinations that the number could represent.
//	A mapping of digit to letters (just like on the telephone buttons) is given below.
//	2→abc; 3→def; 4→ghi; 5→jkl; 6→mno; 7→pqrs; 8→tuv; 9→wxyz
	
	
	static ArrayList<String> result3 = new ArrayList<String>();
    static StringBuilder builder = new StringBuilder();
    static HashMap<Character, char[]> map = new HashMap<Character, char[]>();

	public static ArrayList<String> letterCombinations(String digits) {
		map.put('2', "abc".toCharArray());
		map.put('3', "def".toCharArray());
		map.put('4', "ghi".toCharArray());
		map.put('5', "jkl".toCharArray());
		map.put('6', "mno".toCharArray());
		map.put('7', "pqrs".toCharArray());
		map.put('8', "tuv".toCharArray());
		map.put('9', "wxyz".toCharArray());
        if(digits == null || digits.length() <= 0){
        	result3.add(new String());
        	return result3;
        }
        char[] numbers = digits.toCharArray();
//        System.out.println(map.get(numbers[1]));
        backtrackingOfLetter(numbers, map.get(numbers[0]), numbers.length, 0);
        return result3;
    }
	
	public static void backtrackingOfLetter(char[] number, char[] array, int remain , int start) {
		if(remain < 0){
			return;
		}else if (remain == 0) {
			result3.add(new String(builder));
//			System.out.println(" builder value : " +builder.toString());
		}else {
			int i ;
			for (i = start; i < array.length; i++) {
//				System.out.println("char: " + array[i] + " i:" + i);
				builder.append(array[i]);
			    int length = number.length - remain + 1;
				backtrackingOfLetter(number, length >= number.length? null : map.get(number[length]), 
						remain - 1 , 0);  //寻找下一个,这里对于下一个数组，从0开始
				builder.deleteCharAt(builder.length() - 1);
			}
		}
	}
}
